Khái niệm độ phức tạp truyền thông được đưa ra bởi Andrew Yao năm 1979,[1]khi nghiên cứu về việc hai người độc lập nhau (Alice và Bob) cùng cộng tác để thực hiện một công việc tính toán. Alice nhận được một xâu n-bit, ký hiệu là x, và Bob nhận được một xâu n-bit khác, ký hiệu là y. Mục tiêu là cuối cùng một trong hai người (ví dụ Bob) tính được giá trị một hàm f(x,y) sau khi hai người trao đổi một lượng thông tin ít nhất có thể. Ghi chú là ta không quan tâm đến số phép tính hay lượng bộ nhớ cần dùng. Độ phức tạp truyền thông là ngành nghiên cứu lượng thông tin cần truyền trong những bài toán tính toán phân tán như vậy.Dĩ nhiên họ luôn đạt được mục tiêu bằng cách để Alice gửi toàn bộ xâu n-bit cô nhận được cho Bob, và sau đó Bob tính giá trị hàm số f, nhưng trong nhiều trường hợp, tùy vào hàm f, có thể giải quyết được bài toán với lượng bit cần trao đổi ít hơn n rất nhiều.Bài toán trừu tượng này có nhiều ứng dụng: chẳng hạn trong thiết kế mạch VLSI, ta muốn cực tiểu hóa năng lượng cần dùng bằng cách giảm lượng tín hiệu điện cần gửi đi giữa các thành phần khác nhau trong quá trình tính toán. Bài toán này cũng có ứng dụng trong nghiên cứu cấu trúc dữ liệu, và tối ưu hóa mạng máy tính.[2]